/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/shortest-path-in-undirected-graph
   @Language: C++
   @Datetime: 20-01-19 11:33
   */


/**
 * Definition for Undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */

// Method 1, BFS, Time 369ms
class Solution {
public:
	/**
	 * @param graph: a list of Undirected graph node
	 * @param A: nodeA
	 * @param B: nodeB
	 * @return:  the length of the shortest path
	 */
	int shortestPath(vector<UndirectedGraphNode*> graph, UndirectedGraphNode* A, UndirectedGraphNode* B) {
		// Write your code here
		queue<UndirectedGraphNode*> q({A});
		unordered_set<UndirectedGraphNode*> visit={A};
		for(int path=0; q.size(); ++path){
			for(int size=q.size(); size--; q.pop()){
				const auto &node=q.front();
				if (node->label==B->label) return path;
				for(const auto &n:node->neighbors){
					if (!visit.count(n)) {
						q.push(n);
						visit.insert(n);
					}
				}
			}
		}
		return 0;
	}
};

// Method 2, binary BFS, Time 213ms
class Solution {
public:
	/**
	 * @param graph: a list of Undirected graph node
	 * @param A: nodeA
	 * @param B: nodeB
	 * @return:  the length of the shortest path
	 */
	int shortestPath(vector<UndirectedGraphNode*> graph, UndirectedGraphNode* A, UndirectedGraphNode* B) {
		// Write your code here
		queue<UndirectedGraphNode*> qa({A}), qb({B});
		unordered_map<int, int> visit={{A->label,1},{B->label,2}};
		for(int path=0; !qa.empty() && !qb.empty(); ++path){
			int flag=qa.size()<=qb.size()?1:2;
			auto &q=flag==1?qa:qb;
			for(int size=q.size(); size--; q.pop()){
				const auto &node=q.front();
				if (visit[node->label]==3) return path;
				for(const auto &n:node->neighbors){
					if (visit[n->label]&flag) continue;
					q.push(n);
					visit[n->label]|=flag;
				}
			}
		}
		return 0;
	}
};
